W5. C++ Templates, RANGE Metaprogramming, Smart Pointers

1. Summary

1.1 Why Templates? The Problem of Code Duplication

Imagine you need a function that returns the maximum of two integers. Easy:

int Max(int a, int b) {
    return a > b ? a : b;
}

Now you need the same function for float, double, and a user-defined type Temperature. The straightforward solution is to write a separate function for each type:

float  Max(float a,  float b)  { return a > b ? a : b; }
double Max(double a, double b) { return a > b ? a : b; }
// ... and so on for every type

This approach has critical problems:

• Hard to maintain: Every bug fix must be applied to all copies. Every test must cover all copies.
• Impossible for libraries: A library author cannot know in advance every type a user might need.
• Scales poorly: In large programs (thousands of types), this becomes unmanageable.

The solution is genericity: write the algorithm once and let the compiler generate type-specific versions automatically. C++ achieves this with templates. Other languages use similar mechanisms under different names:

• Ada, Eiffel: Generics
• Java, C#, Rust, Swift, Scala: Generics
• C++: Templates

%%{init: {'theme': 'base', 'themeVariables': { 'fontFamily': 'Helvetica', 'primaryColor': '#e8f4f8', 'primaryTextColor': '#1f2d3d', 'primaryBorderColor': '#355c7d', 'lineColor': '#355c7d', 'secondaryColor': '#d6eef5', 'tertiaryColor': '#fff3cd', 'background': '#ffffff', 'mainBkg': '#e8f4f8', 'secondBkg': '#d6eef5', 'tertiaryBkg': '#fff3cd', 'clusterBkg': '#f9fbfd', 'clusterBorder': '#355c7d', 'edgeLabelBackground': '#ffffff' }}}%%
%%| fig-cap: "One generic template replaces many near-identical type-specific implementations"
%%| fig-width: 6
%%| fig-height: 3
flowchart TB
    Dup["Max(int,int)<br/>Max(float,float)<br/>Max(double,double)<br/>Max(Temperature,Temperature)"]
    Tpl["template<typename T><br/>T Max(T a, T b)"]
    Dup --> Tpl

1.2 Function Templates

1.2.1 Syntax

A function template is a blueprint for a family of functions. Instead of a concrete type like int, you use a type parameter (a placeholder name, conventionally T):

template <typename T>   // Template header: declares T as a type parameter
T Max(T a, T b)         // Template body: uses T wherever the type appears
{
    return a > b ? a : b;
}
// No semicolon after the closing brace

• template – keyword that starts a template declaration
• typename T – declares T as a formal type parameter (you may also write class T — they are equivalent here)
• The template body is identical to what you would write for a concrete type, with T replacing the specific type

1.2.2 Template Instantiation: What Happens Behind the Scenes

When you use a function template, the compiler performs template instantiation: it looks at the types of the actual arguments, generates a concrete function (called a function-by-template), and then compiles it.

double x = 3.5, y = 2.1, res;
res = Max(x, y);   // Compiler sees: both args are double
                   // → generates and compiles: double Max_double(double a, double b) { ... }
                   // → replaces the call with: res = Max_double(x, y);

This entire process is automatic — you do not write Max_double yourself. The compiler does it. The generated name Max_double is a conceptual name; the real compiler uses a technique called name mangling.

Key rules of instantiation:

• The actual type is deduced from the types of arguments — not from the return type.
• Each unique combination of types is instantiated only once, even if you call it many times with those types.
• Each different combination of types produces a separate function-by-template:

res = Max(x, y);          // Generates Max_double
int k = Max(1, (int)res); // Generates Max_int (a different function!)

1.2.3 The Instantiation Algorithm (Step by Step)

When the compiler encounters a call f(actual-arguments):

1. If f is a regular function → compile the call directly.
2. If f is a function template:
   1. Determine the type \(T_i\) of each actual argument.
   2. If the function-by-template for this exact set \(\{T_i\}\) already exists → go to step 3.
   3. Generate the function-by-template by substituting \(T_i\) for each formal type parameter.
   4. Compile the generated function.
3. Generate code for the function call.

1.2.4 Code Bloat

Template instantiation can cause a problem called code bloat: if two separately compiled files both include the same template header and use the same types, the linker ends up with two identical copies of the same function-by-template in the final executable:

T.h          →  File1.cpp (includes T.h) → File1.obj  (contains Max_double)
             →  File2.cpp (includes T.h) → File2.obj  (contains Max_double)
                                         → App.exe    (TWO copies of Max_double!)

Modern linkers can merge duplicates, and the C++ Standard provides mechanisms (explicit instantiation, extern template) to control this, but it is a real concern in large projects.

1.2.5 Requirements on Actual Types

A template does not work with any type — it works only with types that support the operations used inside the template body. For Max, the body contains a > b, so the actual type must have operator>.

class C {
    int m;
public:
    C() : m(0) { }
    // No operator> defined!
};

C c1, c2;
Max(c1, c2);  // Compile error: 'binary >': 'class C' doesn't define this operator

The compiler error message points directly to the generated Max_C function.

Solution: Add the required operator to the class:

class C {
    int m;
public:
    C() : m(0) { }
    bool operator>(const C& c) const { return m > c.m; }
};
// Now Max(c1, c2) works correctly

The general principle: A function template implicitly requires that every actual type supports all operations used inside the template body. Violation is a compile-time error.

1.2.6 C++20 Concepts: Formal Type Requirements

Before C++20, these requirements were informal (written as comments) and only caught at instantiation time — often with confusing error messages. Concepts allow you to formally specify requirements:

template<typename T>
concept GreaterThan =
    requires(T x, T y) { { x > y } -> std::same_as<bool>; };

template<typename T> requires GreaterThan<T>
T Max(T a, T b) {
    return a > b ? a : b;
}

Now if you try to use Max with a type that lacks operator>, the compiler reports a clear error mentioning the violated concept, not a cryptic internal error inside the template body.

1.2.7 Explicit Instantiation of Function Templates

Sometimes the compiler cannot deduce the template type from the arguments — for example, when a function has no arguments:

template <typename T>
int spaceOf() {
    int bytes = sizeof(T);
    return bytes / 4 + (bytes % 4 > 0 ? 1 : 0);
}

// int w = spaceOf();  // ERROR: compiler cannot deduce T

The solution is explicit instantiation — you specify the type in angle brackets at the call site:

int wint = spaceOf<int>();      // Explicitly: T = int
int wdouble = spaceOf<double>(); // Explicitly: T = double

The compiler instantiates the template with the given type, then optionally applies optimization (e.g., sizeof(int) is a compile-time constant, so the whole function may be inlined to a constant):

spaceOf<int>()  →  generates spaceOf_int()  →  inlines to constant 1
int wint = spaceOf<int>();  →  int wint = 1;

1.3 Class Templates

A class template is a blueprint for a family of classes — just as a function template is a blueprint for a family of functions.

• A class is a type.
• A class template is not a type; it is a family of types.

1.3.1 Motivating Example: A Stack

A stack (also called LIFO — Last In, First Out) is a data structure with three fundamental operations:

• push: Insert an element on top.
• pop: Remove and return the top element.
• isEmpty: Check whether the stack is empty.

A non-template C++ implementation for integers looks like this:

class Stack {
    int top;
    int S[100];          // Array of integers
public:
    Stack() : top(-1) { }
    void push(int V) { S[++top] = V; }
    int  pop()       { return S[top--]; }
    bool isEmpty()   { return top < 0; }
};

To create a stack of double values you would need to copy the entire class and replace every int with double. This is the same code-duplication problem as with function templates. The template solution:

template <typename T>       // T is the element type
class Stack {
    int top;
    T S[100];               // Array of T
public:
    Stack() : top(-1) { }
    void push(T V) { S[++top] = V; }
    T    pop()     { return S[top--]; }
    bool isEmpty() { return top < 0; }
};

Now T stands for any type — integer, double, string, or user-defined.

1.3.2 Class Template Instantiation

Unlike function templates (which are instantiated implicitly from argument types), class templates must be instantiated explicitly using the <actual-type> syntax:

Stack<int>    sint;         // Stack of integers
Stack<double> sdouble;      // Stack of doubles
Stack<string> sstr;         // Stack of strings

Stack<float>  sf1, sf2;     // Two stacks of floats
Stack<int>*   arrayOfStacks[10]; // Array of 10 pointers to int-stacks

The notation Stack<int> is a type specifier — it names a class generated by the compiler from the Stack template by substituting int for T. This generated class behaves exactly like an ordinary class.

Using a class-by-template:

Stack<int> s;
s.push(1);
s.push(2);
int v = s.pop();  // v = 2

Type aliases (two equivalent syntaxes):

typedef Stack<double> SD;        // C++98/03
using SD = Stack<double>;        // C++11 (preferred)
SD sd1, sd2;

1.3.3 Templates, Classes, and Instances — Three Levels

It is important to distinguish three conceptually different entities:

Level	Entity	Created by	Exists at
Template	Stack<T> (blueprint)	Programmer	Source code
Class-by-template	Stack<int>, Stack<double>	Compiler (instantiation)	Compile time
Object (instance)	Stack<int> s;	Runtime (new or stack allocation)	Runtime

%%{init: {'theme': 'base', 'themeVariables': { 'fontFamily': 'Helvetica', 'primaryColor': '#e8f4f8', 'primaryTextColor': '#1f2d3d', 'primaryBorderColor': '#355c7d', 'lineColor': '#355c7d', 'secondaryColor': '#d6eef5', 'tertiaryColor': '#fff3cd', 'background': '#ffffff', 'mainBkg': '#e8f4f8', 'secondBkg': '#d6eef5', 'tertiaryBkg': '#fff3cd', 'clusterBkg': '#f9fbfd', 'clusterBorder': '#355c7d', 'edgeLabelBackground': '#ffffff' }}}%%
%%| fig-cap: "From template definition to class template specialization to runtime object"
%%| fig-width: 6.3
%%| fig-height: 3
flowchart LR
    Def["template<typename T><br/>class Stack"]
    Spec1["Stack<int>"]
    Spec2["Stack<double>"]
    Obj["Stack<int> s"]
    Def --> Spec1
    Def --> Spec2
    Spec1 --> Obj

1.3.4 Requirements on Actual Types for Class Templates

Inside Stack, the push method does:

void push(T V) { S[++top] = V; }

Two operations on type T are used:

1. Passing V by value (T V) — invokes the copy constructor.
2. Assigning = V — invokes the assignment operator.

Therefore, to use Stack<MyClass>, MyClass must have a public copy constructor and a public assignment operator. The compiler auto-generates both for most classes, but there are exceptions (e.g., if copying is expensive or explicitly deleted). To avoid invoking the copy constructor on push, pass by reference:

void push(const T& V) { S[++top] = V; }   // No copy constructor needed for the call

Similarly, pop returns by value, which also copies. A common improvement is to return a reference:

T& pop() { return S[top--]; }

1.3.5 Non-Type Template Parameters

Template parameters do not have to be types — they can also be constant values (integers, pointers, etc.). This allows parameterizing the behavior or dimensions of a class at compile time, not just its element type.

The fixed-size array T S[100] inside Stack is a design limitation — every stack has exactly 100 slots regardless of need. We can make the size a template parameter:

template <typename T, int N>    // Two parameters: type T and integer N
class Stack {
    int top;
    T S[N];                      // Size is now N, determined at compile time
public:
    Stack() : top(-1) { }
    void push(const T& V) { S[++top] = V; }
    T    pop()            { top--; return S[top + 1]; }
    bool isEmpty()        { return top < 0; }
};

Usage:

Stack<int, 10>  s10;   // Stack of 10 integers
Stack<double, 50> s50; // Stack of 50 doubles

Important constraint: Non-type template arguments must be compile-time constants. You cannot pass a runtime variable as a non-type template argument.

Allowed non-type arguments:

• Constant integral expressions (e.g., 10, sizeof(int) * 4)
• Names of objects with external linkage
• Addresses of objects/functions with external linkage

1.3.6 Multi-Parameter Class Templates

Templates can have multiple type parameters. A Dictionary (map from keys to values) naturally needs two types:

#include <map>
#include <string>

template<typename K, typename V>
class Dictionary {
    std::map<K, V> data;
public:
    void insert(const K& key, const V& value) {
        data[key] = value;
    }
    V get(const K& key) const {
        auto it = data.find(key);
        if (it != data.end()) return it->second;
        throw std::runtime_error("Key not found");
    }
    bool contains(const K& key) const {
        return data.find(key) != data.end();
    }
    void remove(const K& key) {
        data.erase(key);
    }
};

// Usage:
Dictionary<int, std::string> myDict;
myDict.insert(1, "One");
myDict.insert(2, "Two");
std::cout << myDict.get(1) << std::endl;  // "One"

1.4 Metaprogramming Case Study: RANGE Types

Metaprogramming means using the language’s type system and templates to enforce constraints at compile time rather than at runtime. The RANGE example shows this beautifully.

1.4.1 The Problem with Primitive Integer Types

Consider a variable currentDay that should hold a day of the month (1–31). Using int:

int currentDay, currentMonth;
currentDay = 70;              // Nonsense — but the compiler accepts it!
currentDay = currentMonth + 1; // Mixing day and month? The compiler won't warn.

Languages like Pascal and Ada solve this with range types:

type DayOfMonth = 1..31;  // Pascal

type DayOfMonth is Integer range 1..31;  -- Ada

C++ has no built-in range types. However, using classes and templates, we can build one.

1.4.2 First Attempt: A Naive RANGE Class

The idea: create a class that stores a value together with its allowed boundaries, and checks the value on every modification.

class RANGE {
    int leftBorder;
    int rightBorder;
    int value;
public:
    // Constructor: set borders and initial value
    RANGE(int v, int l, int r) {
        leftBorder = l;
        rightBorder = r;
        value = v;
        check();  // Verify immediately
    }

    // Deleted default constructor: forbid uninitialized RANGE objects
    RANGE() = delete;

    // Copy constructor
    RANGE(const RANGE& r) {
        leftBorder = r.leftBorder;
        rightBorder = r.rightBorder;
        value = r.value;
    }

    // Assignment from another RANGE
    RANGE& operator=(RANGE& r) { value = r.value; return *this; }

    // Assignment from int
    RANGE& operator=(int v) { value = v; check(); return *this; }

    // Increment
    RANGE& operator++() { value++; check(); return *this; }

    // Conversion to int (so RANGE can be used where int is expected)
    operator int() { return value; }

private:
    void check() {
        if (value < leftBorder || value > rightBorder)
            throw std::out_of_range("RANGE value out of bounds");
    }
};

Why does operator= return *this? To support chained assignments: a = b = c requires the assignment to return a reference to the left operand.

Usage:

RANGE range(0, -10, 10);  // value=0, allowed: [-10, 10]
range = 5;    // OK
range = 15;   // throws exception
++range;      // increments, checks
int i = range; // uses operator int()

1.4.3 Problems with the Naive Approach

This works but has two fundamental weaknesses:

Problem 1 — Boundaries are value attributes, not type attributes:

RANGE a(0, -5, 5);
RANGE b(3, 1, 10);

a = b;  // Compiles! But semantically wrong — different ranges!

a and b are variables of the same type (RANGE), even though they represent completely different value domains. Ideally, RANGE(-5,5) and RANGE(1,10) should be different types so that assigning one to the other is a compile-time error.

Problem 2 — Storage overhead:

Each RANGE object carries three integers: value, leftBorder, rightBorder. The borders never change after construction — they are logically part of the type, not the value. There is no reason to store them repeatedly in every object.

1.4.4 Template Solution for RANGE

The fix is to make the borders template parameters (compile-time constants) instead of runtime data members. Then each (leftBorder, rightBorder) pair creates a distinct type:

template <int leftBorder, int rightBorder>
class RANGE {
    int value;            // Only member: the stored value
    RANGE() = delete;     // No default constructor

public:
    RANGE(int v)             { value = v; check(); }
    RANGE(const RANGE& r)    { value = r.value; }
    RANGE& operator=(RANGE& r)  { value = r.value; return *this; }
    RANGE& operator=(int v)     { value = v; check(); return *this; }
    RANGE& operator++()         { value++; check(); return *this; }
    operator long()             { return (long)value; }

private:
    void check() {
        if (value < leftBorder || value > rightBorder)
            throw std::out_of_range("RANGE value out of bounds");
    }
};

Now:

RANGE<-5, 5>  a(0);   // Type: RANGE<-5,5>, stores only one int
RANGE<1, 10>  b(3);   // Type: RANGE<1,10>, completely different type

a = b;  // COMPILE ERROR: different types — assignment operator is type-safe!

RANGE<-5,5> and RANGE<1,10> are different classes generated from the same template. Each stores only one integer (the value); the borders are baked into the type name at compile time — zero runtime overhead.

Type aliases make usage convenient:

typedef RANGE<-5, 5>  myTinyInt;   // C++98
using myTinyInt = RANGE<-5, 5>;    // C++11 (preferred)

myTinyInt i = 2;   // Clean, type-safe syntax

The family of types RANGE<-5,5>, RANGE<1,10>, RANGE<100,1000> etc. are all distinct types generated from the same template. They are incompatible with each other, just like int and double are incompatible.

1.5 Problems with Raw C/C++ Pointers

Before learning how to fix pointer problems, it is essential to understand what those problems are. Scott Meyers identified six categories of problems with raw pointers (plus additional ones).

1.5.1 Ambiguity: Single Object vs Array (Problems 1 & 4)

A pointer T* ptr can point to either a single object or the first element of an array — there is no way to tell from the pointer type alone:

int x;
int A1[10];
int* A2 = &x;
int* A = cond ? A1 : A2;

int res = A[5];  // Is this valid? Depends on cond — undefined behavior!

Consequently, there are two different deallocation operators — delete ptr (for single objects) and delete[] ptr (for arrays) — and using the wrong one is undefined behavior.

1.5.2 Ownership Ambiguity (Problem 2)

Looking at a pointer declaration, you cannot tell whether the function “owns” the object (i.e., is responsible for destroying it):

void fun(T* ptr) {
    // Do some work with *ptr
    // Should we destroy it? We don't know!
    return;
}

This ambiguity leads to memory leaks (if nobody deletes) or double-deletion (if multiple callers each try to delete).

1.5.3 Destruction Method Ambiguity (Problem 3)

Even if you know you must destroy the object, you may not know how:

void fun(T* ptr) {
    // Work...
    free(ptr);         // Correct? Or should it be:
    // myDealloc(ptr); // a custom deallocator?
    // delete ptr;     // Or this?
}

Different allocation schemes require different deallocation functions.

1.5.4 Double Destruction (Problem 5)

When multiple code paths share a pointer, it is easy to destroy the object twice:

void lib_fun(T* ptr) {
    // Does lib_fun delete the object? Hard to know without reading all source code.
}

void user_fun() {
    T* ptr = new T();
    lib_fun(ptr);
    delete ptr;  // Is this a double-delete if lib_fun already deleted it?
}

Double-deletion is undefined behavior — it can corrupt the heap and cause security vulnerabilities.

1.5.5 Dangling Pointers (Problem 6)

There is no built-in way to check whether a pointer still points to a valid, live object:

T* ptr = new T();
if (condition) delete ptr;
// ...
// Long code later...
// Is ptr still valid? Cannot know without tracking control flow manually.

A dangling pointer is a pointer that refers to memory that has already been freed. Dereferencing it is undefined behavior.

Classic dangling pointer with stack allocation:

int* p;

void f() {
    int A[10];
    p = A + 2;   // p points into f's stack frame
}               // A goes out of scope — memory is freed

int main() {
    f();
    *p = 777;   // p is now dangling — undefined behavior!
}

When f returns, its entire stack frame (including A) is gone. p still holds an address into that now-invalid memory.

%%{init: {'theme': 'base', 'themeVariables': { 'fontFamily': 'Helvetica', 'primaryColor': '#e8f4f8', 'primaryTextColor': '#1f2d3d', 'primaryBorderColor': '#355c7d', 'lineColor': '#355c7d', 'secondaryColor': '#d6eef5', 'tertiaryColor': '#fff3cd', 'background': '#ffffff', 'mainBkg': '#e8f4f8', 'secondBkg': '#d6eef5', 'tertiaryBkg': '#fff3cd', 'clusterBkg': '#f9fbfd', 'clusterBorder': '#355c7d', 'edgeLabelBackground': '#ffffff' }}}%%
%%| fig-cap: "Dangling pointer: pointer survives after the stack object it points to has been destroyed"
%%| fig-width: 6.2
%%| fig-height: 3.2
flowchart TB
    subgraph Frame["Function f stack frame"]
      A["A : int = 42"]
      P["p = &A"]
    end
    After["f returns<br/>stack frame removed"]
    Dangling["p still stores old address<br/>dangling pointer"]
    Frame --> After --> Dangling
    style Frame fill:#f9fbfd,stroke:#355c7d,color:#1f2d3d
    style A fill:#d6eef5,stroke:#355c7d,color:#1f2d3d
    style P fill:#e8f4f8,stroke:#355c7d,color:#1f2d3d
    style After fill:#eef3f7,stroke:#355c7d,color:#1f2d3d
    style Dangling fill:#f9d9e2,stroke:#355c7d,color:#1f2d3d

1.5.6 Memory Leaks (Problem 7)

If the last (or only) pointer to a dynamically allocated object goes out of scope without delete being called, the object persists in memory but is forever unreachable — a memory leak:

void f() {
    int* p = new int(42);  // Dynamic object allocated on heap
    // ... (no delete)
}  // p goes out of scope; the int(42) still lives on the heap but cannot be reached!

In a long-running application, accumulated leaks can exhaust all available memory.

%%{init: {'theme': 'base', 'themeVariables': { 'fontFamily': 'Helvetica', 'primaryColor': '#e8f4f8', 'primaryTextColor': '#1f2d3d', 'primaryBorderColor': '#355c7d', 'lineColor': '#355c7d', 'secondaryColor': '#d6eef5', 'tertiaryColor': '#fff3cd', 'background': '#ffffff', 'mainBkg': '#e8f4f8', 'secondBkg': '#d6eef5', 'tertiaryBkg': '#fff3cd', 'clusterBkg': '#f9fbfd', 'clusterBorder': '#355c7d', 'edgeLabelBackground': '#ffffff' }}}%%
%%| fig-cap: "Memory leak: the heap object remains allocated after the last owning pointer disappears"
%%| fig-width: 6
%%| fig-height: 3
flowchart LR
    P["p : int*"]
    H["heap object<br/>new int(42)"]
    Gone["p goes out of scope"]
    Leak["unreachable heap object<br/>memory leak"]
    P --> H
    H --> Gone --> Leak

1.6 Smart Pointers

Smart pointers are class templates that wrap raw pointers and provide automatic resource management. They add “smart” behavior — like automatic deletion — without losing the efficiency of raw pointers. All require #include <memory>.

The key design pattern behind smart pointers is RAII — Resource Acquisition Is Initialization: resources are acquired in the constructor and released in the destructor. Since destructors are called automatically when objects go out of scope, resource cleanup is guaranteed.

1.6.1 General Idea: A Simple Smart Pointer

A minimal smart pointer wraps a raw pointer and deletes it automatically when it goes out of scope:

template <typename T>
class smart_pointer {
    T* obj;           // The underlying raw pointer
public:
    smart_pointer(T* o) : obj(o) { }    // Takes ownership
    ~smart_pointer() { delete obj; }    // Guaranteed cleanup

    T* operator->() { return obj; }     // Arrow dereference
    T& operator*()  { return *obj; }    // Star dereference
};

{
    smart_pointer<MyClass> sp(new MyClass());
    sp->someMethod();  // Works like a raw pointer
}  // Destructor called — MyClass object is deleted automatically

No delete required from the caller. C++ provides three production-quality smart pointer templates.

1.6.2 unique_ptr — Exclusive Ownership

unique_ptr implements exclusive ownership: at any given moment, exactly one unique_ptr owns the object. This is enforced by the compiler: unique_ptr cannot be copied.

#include <memory>

std::unique_ptr<int> x(new int(42));
std::unique_ptr<int> y;

y = x;                   // COMPILE ERROR: copy is forbidden
std::unique_ptr<int> z(x); // COMPILE ERROR: copy constructor is deleted

Transferring ownership is possible with std::move, which moves ownership from one pointer to another and nullifies the source:

y = std::move(x);   // y now owns the object; x becomes nullptr

C++14 factory function (make_unique) — preferred over new because it is exception-safe:

auto x = std::make_unique<int>(42);   // No explicit new

Key member functions:

• x.get() — returns the underlying raw pointer (without releasing ownership)
• x.reset() — destroys the owned object and sets the pointer to nullptr
• x.release() — returns the raw pointer and relinquishes ownership (caller is now responsible)

unique_ptr solves:

• Memory leaks (automatic deletion)
• Double deletion (only one owner)
• Ownership clarity (intent is explicit in the type)

1.6.3 shared_ptr — Cooperative Ownership and ARC

shared_ptr implements shared ownership: multiple shared_ptr instances can all own the same object. The object is deleted automatically when the last shared_ptr to it is destroyed or reset.

The mechanism is Automatic Reference Counting (ARC): each shared_ptr group maintains an internal reference counter. The counter increments when a new shared_ptr is created from an existing one, and decrements when one is destroyed. When the counter reaches zero, the object is deleted.

auto x = std::make_shared<int>(42);  // ref count = 1
{
    auto y = x;                       // ref count = 2 (y shares ownership)
    auto z = x;                       // ref count = 3
}  // y and z go out of scope — ref count drops to 1
// x goes out of scope — ref count drops to 0 — object deleted

Where is the reference counter stored? Together with the object, in a control block allocated alongside the managed object (especially when using make_shared). This is why shared_ptr is represented internally by two pointers: one to the object, one to the control block.

Key member functions:

• x.use_count() — returns the current reference count
• x.get(), x.reset(), x.swap() — same semantics as in unique_ptr
• operator bool() — tests whether the pointer is non-null

shared_ptr overhead: Two pointers per instance, atomic reference count operations (for thread safety). Use unique_ptr when sharing is not needed.

%%{init: {'theme': 'base', 'themeVariables': { 'fontFamily': 'Helvetica', 'primaryColor': '#e8f4f8', 'primaryTextColor': '#1f2d3d', 'primaryBorderColor': '#355c7d', 'lineColor': '#355c7d', 'secondaryColor': '#d6eef5', 'tertiaryColor': '#fff3cd', 'background': '#ffffff', 'mainBkg': '#e8f4f8', 'secondBkg': '#d6eef5', 'tertiaryBkg': '#fff3cd', 'clusterBkg': '#f9fbfd', 'clusterBorder': '#355c7d', 'edgeLabelBackground': '#ffffff' }}}%%
%%| fig-cap: "shared_ptr ownership: several handles share one object through a common reference count"
%%| fig-width: 6.2
%%| fig-height: 3
flowchart LR
    A["shared_ptr a"]
    B["shared_ptr b"]
    RC["control block<br/>ref count = 2"]
    Obj["managed object"]
    A --> RC
    B --> RC
    RC --> Obj

1.6.4 Circular References: The shared_ptr Problem

shared_ptr with ARC has one critical limitation: circular references. If two objects each hold a shared_ptr to the other, their reference counts will never reach zero — neither object will ever be deleted:

class Bar;
class Foo {
public:
    std::shared_ptr<Bar> bar;
};
class Bar {
public:
    std::shared_ptr<Foo> foo;
};

void fun() {
    auto foo = std::make_shared<Foo>();  // foo ref count = 1
    foo->bar = std::make_shared<Bar>();  // bar ref count = 1
    foo->bar->foo = foo;                 // foo ref count = 2 (circular!)
}
// fun exits: foo variable destroyed → foo ref count = 1 (not 0!)
//            bar's shared_ptr<Foo> still holds foo
// Both objects are leaked!

%%{init: {'theme': 'base', 'themeVariables': { 'fontFamily': 'Helvetica', 'primaryColor': '#e8f4f8', 'primaryTextColor': '#1f2d3d', 'primaryBorderColor': '#355c7d', 'lineColor': '#355c7d', 'secondaryColor': '#d6eef5', 'tertiaryColor': '#fff3cd', 'background': '#ffffff', 'mainBkg': '#e8f4f8', 'secondBkg': '#d6eef5', 'tertiaryBkg': '#fff3cd', 'clusterBkg': '#f9fbfd', 'clusterBorder': '#355c7d', 'edgeLabelBackground': '#ffffff' }}}%%
%%| fig-cap: "Circular shared_ptr references prevent reference counts from reaching zero"
%%| fig-width: 6.2
%%| fig-height: 3.2
flowchart LR
    Foo["Foo object"]
    Bar["Bar object"]
    Foo -- "shared_ptr<Bar>" --> Bar
    Bar -- "shared_ptr<Foo>" --> Foo
    Leak["both stay alive<br/>reference cycle"]
    Foo --> Leak
    Bar --> Leak

1.6.5 weak_ptr — Breaking Circular References

weak_ptr is a non-owning observer of an object managed by shared_ptr. It does not increment the reference count, so it does not prevent the object from being deleted. However, it can check whether the object still exists and temporarily promote itself to a shared_ptr for safe access.

auto shared = std::make_shared<MyObj>();  // ref count = 1
std::weak_ptr<MyObj> weak(shared);        // ref count still = 1 (weak does not count)

shared = nullptr;                          // ref count drops to 0 — object deleted
// weak now points to an expired (destroyed) object

if (weak.expired()) {
    // Object is gone
}

auto temp = weak.lock();  // Attempts to get a shared_ptr
if (temp) {
    // Object still exists — use temp safely
}

Solving circular references with weak_ptr: Break one link in the cycle by making it a weak_ptr:

class Bar;
class Foo {
public:
    std::shared_ptr<Bar> bar;   // Foo owns Bar (strong reference)
};
class Bar {
public:
    std::weak_ptr<Foo> foo;     // Bar observes Foo but does NOT own it (weak reference)
};

void fun() {
    auto foo = std::make_shared<Foo>();  // foo ref count = 1
    foo->bar = std::make_shared<Bar>();  // bar ref count = 1
    foo->bar->foo = foo;                 // foo ref count stays 1 (weak_ptr!)
}
// fun exits: foo ref count = 1 → 0 → Foo deleted → Bar's shared_ptr lost → bar ref count = 1 → 0 → Bar deleted
// No leak!

Summary of smart pointer types:

Type	Ownership	Copy	ref count	Use case
unique_ptr	Exclusive	No (move only)	No	Single owner, no sharing
shared_ptr	Shared	Yes	Yes (ARC)	Multiple owners
weak_ptr	None (observer)	Yes	No	Break cycles, optional references

---

2. Definitions

• Template: A C++ language feature that allows writing generic code parameterized by types or compile-time values, so the compiler can generate concrete functions or classes for any given type.
• Function template: A template that acts as a blueprint for a family of functions; the compiler generates a concrete function (function-by-template) each time the template is used with a specific type.
• Class template: A template that acts as a blueprint for a family of classes; must be explicitly instantiated with TemplateName<ActualType> before use.
• Template parameter: A placeholder in a template definition — either a type parameter (declared with typename T or class T) or a non-type parameter (a compile-time constant, e.g., int N).
• Template instantiation: The process by which the compiler generates a concrete function or class from a template by substituting actual types (or values) for formal type parameters.
• Function-by-template: A concrete function generated by instantiating a function template with a specific type (e.g., Max_double from Max<T>).
• Class-by-template: A concrete class generated by instantiating a class template with a specific type (e.g., Stack<int> from Stack<T>).
• Implicit instantiation: Template instantiation triggered automatically by the compiler when a function template is called with typed arguments.
• Explicit instantiation: Template instantiation where the programmer specifies the type explicitly using angle-bracket syntax (e.g., spaceOf<int>()), needed when the compiler cannot deduce the type from arguments.
• Non-type template parameter: A template parameter that is a compile-time constant value (typically an integer), rather than a type; e.g., template <typename T, int N>.
• Code bloat: The problem where template instantiation produces multiple copies of the same function-by-template in separate object files, leading to a larger-than-necessary executable.
• Type requirements: The set of operations a type must support to be used as an actual type parameter in a template; violations produce compile-time errors.
• Concept (C++20): A formal, compiler-checkable specification of requirements on template type parameters, enabling clearer error messages when requirements are violated.
• Genericity: The ability to write code that works with any type satisfying certain requirements, rather than being tied to specific concrete types.
• RANGE type: A user-defined type that restricts integer values to a specified compile-time interval; implemented via a class template with non-type parameters for the boundaries.
• Metaprogramming: A programming technique where the program manipulates code (types, values, structures) at compile time using the template system, rather than at runtime.
• Raw pointer: A plain C/C++ pointer (T*) with no built-in ownership semantics or automatic cleanup.
• Dangling pointer: A pointer that refers to memory that has already been freed or gone out of scope; dereferencing it is undefined behavior.
• Memory leak: The situation where a dynamically allocated object is never freed because the last pointer to it has gone out of scope; the memory remains allocated but inaccessible.
• RAII (Resource Acquisition Is Initialization): A C++ design pattern where a resource (memory, file handle, mutex, etc.) is acquired in a constructor and released in the destructor, guaranteeing cleanup when the object goes out of scope.
• Smart pointer: A class template that wraps a raw pointer and adds automatic resource management (and possibly ownership tracking) via RAII.
• unique_ptr: A smart pointer implementing exclusive ownership — only one unique_ptr may own an object at a time; the object is deleted when the unique_ptr is destroyed. Cannot be copied; ownership transferred via std::move.
• shared_ptr: A smart pointer implementing shared ownership via Automatic Reference Counting (ARC); the object is deleted when the last shared_ptr pointing to it is destroyed.
• weak_ptr: A non-owning observer that references an object managed by shared_ptr without incrementing its reference count; used to break circular references. Access requires converting to shared_ptr via lock().
• Automatic Reference Counting (ARC): A memory management strategy where an integer counter tracks the number of owning references to an object; the object is destroyed when the count reaches zero.
• Reference count: The integer maintained by shared_ptr representing how many shared_ptr instances currently own a given object.
• Circular reference: A situation where two or more objects hold shared_ptr pointers to each other, forming a cycle; their reference counts never reach zero, causing a memory leak.
• std::move: A cast to an rvalue reference; used to transfer ownership of a unique_ptr (or other move-only type) without copying.
• make_unique<T>(...) (C++14): Factory function that creates an object and wraps it in a unique_ptr in a single exception-safe step.
• make_shared<T>(...): Factory function that creates an object and its reference-count control block together, wrapping the result in a shared_ptr.
• weak_ptr::expired(): Returns true if the object the weak_ptr was observing has already been destroyed (i.e., reference count reached zero).
• weak_ptr::lock(): Attempts to obtain a shared_ptr to the observed object; returns an empty shared_ptr if the object no longer exists.
• Control block: An internal data structure allocated alongside the managed object in shared_ptr; stores the reference count and weak reference count.

---

3. Examples

3.1. Generic Stack with Specialized StringStack (Lab 5, Task 1)

Implement a generic GenericStack<T> class template that supports push(), pop(), and peek(). The stack should resize dynamically. Then create a StringStack subclass that:

• Rejects empty strings on push()
• Adds a concatTopTwo() method that pops the top two strings, concatenates them, and pushes the result

Include error handling for edge cases.

Click to see the solution

Key Concept: Templates and inheritance work together — StringStack inherits from GenericStack<string>, gaining all generic functionality and customizing or extending it for strings.

#include <iostream>
#include <vector>
#include <stdexcept>
#include <string>
using namespace std;

// -------- GenericStack<T> --------
template <typename T>
class GenericStack {
protected:
    vector<T> data;   // vector handles dynamic resizing automatically

public:
    // Constructor: optional initial capacity (vector still grows as needed)
    explicit GenericStack(int initialCapacity = 0) {
        data.reserve(initialCapacity);
    }

    virtual ~GenericStack() = default;

    // Insert element on top
    virtual void push(const T& element) {
        data.push_back(element);
    }

    // Remove and return top element
    virtual T pop() {
        if (isEmpty()) throw underflow_error("pop() on empty stack");
        T top = data.back();
        data.pop_back();
        return top;
    }

    // Return top element without removing it
    virtual T peek() const {
        if (isEmpty()) throw underflow_error("peek() on empty stack");
        return data.back();
    }

    bool isEmpty() const { return data.empty(); }
    int  size()    const { return (int)data.size(); }
};

// -------- StringStack --------
class StringStack : public GenericStack<string> {
public:
    explicit StringStack(int capacity = 0) : GenericStack<string>(capacity) { }

    // Override push: reject empty strings
    void push(const string& s) override {
        if (s.empty())
            throw invalid_argument("StringStack::push: empty string not allowed");
        GenericStack<string>::push(s);   // Delegate to base
    }

    // New method: pop top two strings, concatenate, push result
    void concatTopTwo() {
        if (size() < 2)
            throw underflow_error("concatTopTwo: need at least 2 elements");
        string second = pop();  // top
        string first  = pop();  // second from top
        push(first + second);   // push concatenation
    }
};

int main() {
    cout << "=== GenericStack<int> ===" << endl;
    GenericStack<int> intStack(5);
    intStack.push(10);
    intStack.push(20);
    intStack.push(30);
    cout << "Peek: " << intStack.peek() << endl;  // 30
    cout << "Pop:  " << intStack.pop()  << endl;  // 30
    cout << "Pop:  " << intStack.pop()  << endl;  // 20

    cout << "\n=== StringStack ===" << endl;
    StringStack ss;
    ss.push("Hello, ");
    ss.push("World!");
    cout << "Top before concat: " << ss.peek() << endl;  // "World!"

    ss.concatTopTwo();
    cout << "After concatTopTwo: " << ss.peek() << endl; // "Hello, World!"

    // Try pushing empty string
    try {
        ss.push("");
    } catch (const invalid_argument& e) {
        cout << "Error: " << e.what() << endl;
    }

    // Try concatTopTwo on single element
    try {
        ss.concatTopTwo();
    } catch (const underflow_error& e) {
        cout << "Error: " << e.what() << endl;
    }

    return 0;
}

Output:

=== GenericStack<int> ===
Peek: 30
Pop:  30
Pop:  20

=== StringStack ===
Top before concat: World!
After concatTopTwo: Hello, World!
Error: StringStack::push: empty string not allowed
Error: concatTopTwo: need at least 2 elements

1. Template base: GenericStack<T> works with any type; vector<T> handles dynamic sizing automatically.
2. Inheritance: StringStack : public GenericStack<string> inherits all generic operations.
3. Override push: Adds validation before delegating to the base implementation via GenericStack<string>::push(s).
4. concatTopTwo: Pops in LIFO order — the first popped is the top (second word), the second popped is below (first word). They must be concatenated in the correct order.
5. Virtual destructor in base: virtual ~GenericStack() = default ensures correct destruction through base pointers.

Answer: See full implementation above. Inheritance combined with templates allows clean specialization of generic containers.

3.2. Smart Pointers in Practice: Box Class (Lab 5, Task 2)

Create a class Box with an integer value, a constructor, and a destructor (with output). Then implement and demonstrate:

(a) create_unique(int val) — creates a Box via unique_ptr, demonstrates ownership transfer, and returns the value inside the Box.

(b) create_shared_boxes() — creates two shared_ptr<Box> instances and demonstrates how the reference count changes.

(c) A weak_ptr<Box> example — show checking validity and converting weak_ptr to shared_ptr for access. Explain how weak_ptr solves circular references.

Click to see the solution

Key Concept: Each smart pointer type has a distinct ownership model. unique_ptr → single owner, shared_ptr → shared ownership with ARC, weak_ptr → non-owning observer.

#include <iostream>
#include <memory>
using namespace std;

// ---- Box class ----
class Box {
public:
    int value;

    Box(int v) : value(v) {
        cout << "Box(" << value << ") created\n";
    }
    ~Box() {
        cout << "Box(" << value << ") destroyed\n";
    }
};

// ---- (a) unique_ptr: exclusive ownership ----
int create_unique(int val) {
    auto box = make_unique<Box>(val);   // Box created, ref count = 1 (conceptually)
    cout << "box value: " << box->value << endl;

    // Transfer ownership: box2 takes over, box becomes null
    auto box2 = move(box);
    cout << "After move: box is " << (box ? "valid" : "null") << endl;
    cout << "box2 value: " << box2->value << endl;

    int result = box2->value;
    return result;
    // box2 goes out of scope → Box destroyed automatically
}

// ---- (b) shared_ptr: cooperative ownership ----
void create_shared_boxes() {
    auto boxA = make_shared<Box>(10);   // ref count = 1
    cout << "boxA ref count: " << boxA.use_count() << endl;  // 1

    auto boxB = make_shared<Box>(20);   // ref count = 1
    cout << "boxB ref count: " << boxB.use_count() << endl;  // 1

    {
        auto boxA2 = boxA;              // ref count = 2 (shared ownership)
        cout << "After boxA2 = boxA, ref count: " << boxA.use_count() << endl;  // 2

        auto boxA3 = boxA;              // ref count = 3
        cout << "After boxA3 = boxA, ref count: " << boxA.use_count() << endl;  // 3
    }
    // boxA2 and boxA3 go out of scope → ref count = 1, object NOT deleted
    cout << "After scope: boxA ref count: " << boxA.use_count() << endl;  // 1
}
// boxA goes out of scope → ref count = 0 → Box(10) destroyed

// ---- (c) weak_ptr: non-owning reference ----
void demonstrate_weak() {
    auto shared = make_shared<Box>(42);  // ref count = 1
    weak_ptr<Box> weak(shared);          // ref count still = 1

    cout << "shared ref count: " << shared.use_count() << endl;  // 1
    cout << "weak expired? "     << weak.expired() << endl;       // 0 (false)

    // Safe access via lock()
    if (auto temp = weak.lock()) {
        cout << "Accessed via weak: " << temp->value << endl;  // 42
    }

    shared.reset();  // Explicitly destroy the shared_ptr → ref count = 0 → Box destroyed
    cout << "After reset, weak expired? " << weak.expired() << endl;  // 1 (true)

    if (!weak.lock()) {
        cout << "Object is gone — weak_ptr is safe to use (returns null)\n";
    }
}

int main() {
    cout << "=== (a) unique_ptr ===" << endl;
    int v = create_unique(100);
    cout << "Returned value: " << v << "\n" << endl;

    cout << "=== (b) shared_ptr ===" << endl;
    create_shared_boxes();
    cout << endl;

    cout << "=== (c) weak_ptr ===" << endl;
    demonstrate_weak();

    return 0;
}

Output:

=== (a) unique_ptr ===
Box(100) created
box value: 100
After move: box is null
box2 value: 100
Box(100) destroyed
Returned value: 100

=== (b) shared_ptr ===
Box(10) created
boxA ref count: 1
Box(20) created
boxB ref count: 1
After boxA2 = boxA, ref count: 2
After boxA3 = boxA, ref count: 3
After scope: boxA ref count: 1
Box(10) destroyed
Box(20) destroyed

=== (c) weak_ptr ===
shared ref count: 1
weak expired? 0
Accessed via weak: 42
Box(42) destroyed
After reset, weak expired? 1
Object is gone — weak_ptr is safe to use (returns null)

1. unique_ptr (a): move(box) transfers ownership and nullifies box. The object is destroyed when box2 leaves create_unique’s scope.
2. shared_ptr (b): Each copy of a shared_ptr (assignment or copy construction) increments use_count(). When all copies go out of scope, use_count() reaches 0 and the object is destroyed.
3. weak_ptr (c):
   • weak_ptr<Box> weak(shared) creates an observer without incrementing the ref count.
   • shared.reset() drops the ref count to 0 → Box is destroyed.
   • weak.expired() returns true after destruction.
   • weak.lock() returns an empty shared_ptr safely — no undefined behavior.
4. Circular reference solution: If Box contained a shared_ptr<Box> pointing to another Box that pointed back, neither would be deleted. Making one of those links weak_ptr<Box> breaks the cycle.

Answer: See complete implementation above demonstrating all three smart pointer types and their lifetime semantics.

3.3. Max Function Template: Find the Maximum of Two Values (Lecture 5, Example 1)

Write a function template Max that returns the maximum of two values of any type that supports the > operator. Demonstrate its use with int, double, and a user-defined class.

Click to see the solution

Key Concept: A function template is written once with a type placeholder T. The compiler generates concrete versions (Max_int, Max_double, etc.) on demand based on the argument types at each call site.

#include <iostream>
using namespace std;

// Function template: works for any type T that has operator>
template <typename T>
T Max(T a, T b) {
    return a > b ? a : b;
}

// A user-defined class that satisfies the template requirement (has operator>)
class Temperature {
    double celsius;
public:
    Temperature(double c) : celsius(c) { }
    bool operator>(const Temperature& t) const { return celsius > t.celsius; }
    double value() const { return celsius; }
};

int main() {
    // Implicit instantiation for int (compiler generates Max_int)
    cout << Max(3, 7) << endl;           // 7

    // Implicit instantiation for double (compiler generates Max_double)
    cout << Max(3.14, 2.71) << endl;     // 3.14

    // Implicit instantiation for Temperature (compiler generates Max_Temperature)
    Temperature t1(36.6), t2(38.2);
    cout << Max(t1, t2).value() << endl; // 38.2

    return 0;
}

1. Template declaration: template <typename T> introduces type parameter T. The body return a > b ? a : b; uses T wherever a type is needed.
2. Implicit instantiation: When the compiler sees Max(3, 7), it deduces T = int from the argument types and generates int Max_int(int a, int b) internally.
3. Type requirement: Temperature must have operator> — without it, the compiler reports an error inside the generated Max_Temperature function.
4. Separate instantiations: Max_int, Max_double, and Max_Temperature are three distinct functions in the compiled output.

Answer: The template generates three functions from one definition. Output: 7, 3.14, 38.2.

3.4. alignArray: Converting a Specific Function to a Template (Lecture 5, Example 2)

Given the following integer-specific function, convert it into a function template that works with arrays of any numeric type. Declare a class that satisfies the template’s requirements, then demonstrate the template with an array of that class.

void alignArray(int* array, int size, int barrier) {
    for (int i = 0; i < size; i++) {
        if      (array[i] < barrier) array[i] += 2;
        else if (array[i] > barrier) array[i] -= 2;
    }
}

Click to see the solution

Key Concept: Identify which operations the function applies to the element type, then make those the requirements on the template type parameter.

1. Identify operations used on elements: <, >, +=, -=. The type T must support all four.
2. Write the template:

#include <iostream>
using namespace std;

template <typename T>
void alignArray(T* array, int size, T barrier) {
    for (int i = 0; i < size; i++) {
        if      (array[i] < barrier) array[i] += 2;
        else if (array[i] > barrier) array[i] -= 2;
    }
}

3. Declare a class satisfying requirements:

class Score {
    int val;
public:
    Score(int v = 0) : val(v) { }
    bool operator<(const Score& s) const { return val < s.val; }
    bool operator>(const Score& s) const { return val > s.val; }
    Score& operator+=(int n) { val += n; return *this; }
    Score& operator-=(int n) { val -= n; return *this; }
    int value() const { return val; }
};

4. Demonstrate with the class:

int main() {
    // Demo with int
    int intArr[] = {1, 5, 10, 3, 7};
    alignArray(intArr, 5, 5);
    for (int x : intArr) cout << x << " ";  // 3 5 8 5 5
    cout << endl;

    // Demo with Score
    Score scores[] = {Score(1), Score(8), Score(5), Score(3)};
    alignArray(scores, 4, Score(5));
    for (auto& s : scores) cout << s.value() << " ";  // 3 6 5 5
    cout << endl;

    return 0;
}

Answer: The template parameterizes both the element type and the barrier type as T. Any type supporting <, >, +=, -= satisfies the requirements.

3.5. Stack Class Template with Non-type Size Parameter (Lecture 5, Example 3)

Implement a generic Stack class template parameterized by both the element type T and the maximum size N. Demonstrate creating stacks of different types and sizes.

Click to see the solution

Key Concept: Non-type template parameters allow compile-time configuration of class dimensions. Stack<int,10> and Stack<int,50> are different types.

#include <iostream>
#include <stdexcept>
using namespace std;

template <typename T, int N>
class Stack {
    int top;
    T S[N];          // Array size N is a compile-time constant
public:
    Stack() : top(-1) { }

    void push(const T& V) {
        if (top >= N - 1) throw overflow_error("Stack is full");
        S[++top] = V;
    }

    T pop() {
        if (top < 0) throw underflow_error("Stack is empty");
        return S[top--];
    }

    T peek() const {
        if (top < 0) throw underflow_error("Stack is empty");
        return S[top];
    }

    bool isEmpty() const { return top < 0; }
    bool isFull()  const { return top >= N - 1; }
};

int main() {
    Stack<int, 10> intStack;
    intStack.push(1);
    intStack.push(2);
    intStack.push(3);
    cout << intStack.pop() << endl;  // 3 (LIFO order)
    cout << intStack.pop() << endl;  // 2

    Stack<string, 5> strStack;
    strStack.push("hello");
    strStack.push("world");
    cout << strStack.pop() << endl;  // "world"

    // Stack<int, 10> and Stack<int, 50> are DIFFERENT types:
    // Stack<int, 50> bigStack = intStack;  // COMPILE ERROR

    return 0;
}

1. Template declaration: template <typename T, int N> — two parameters: element type and capacity.
2. Array: T S[N] — N is evaluated at compile time; valid as an array size.
3. LIFO semantics: push increments top before writing; pop reads at top then decrements.
4. Bounds checking: Throws standard exceptions on overflow/underflow.

Answer: Stack<int,10> and Stack<string,5> are independent types generated from the same template. Output: 3, 2, world.

3.6. spaceOf: Explicit Function Template Instantiation (Lecture 5, Example 4)

Write a function template spaceOf<T>() that calculates how many 32-bit words (each 4 bytes) are needed to store a value of type T. Demonstrate explicit instantiation for several types.

Click to see the solution

Key Concept: When a function template has no arguments from which the compiler can deduce T, you must provide the type explicitly using <T> at the call site.

#include <iostream>
using namespace std;

template <typename T>
int spaceOf() {
    int bytes = sizeof(T);
    // Number of 32-bit words: ceiling division by 4
    return bytes / 4 + (bytes % 4 > 0 ? 1 : 0);
}

class MyData {
    double x, y, z;    // 3 doubles = 24 bytes
    int flag;          // 4 bytes
    // Total: 28 bytes = 7 × 4-byte words
};

int main() {
    // Cannot call spaceOf() without explicit type — no arguments to deduce from
    cout << spaceOf<int>()    << endl;    // 4 bytes  → 1 word
    cout << spaceOf<double>() << endl;    // 8 bytes  → 2 words
    cout << spaceOf<char>()   << endl;    // 1 byte   → 1 word (ceiling)
    cout << spaceOf<MyData>() << endl;    // 28+ bytes → 7+ words (depends on padding)

    // The compiler optimizes: sizeof(int)=4 is a compile-time constant,
    // so spaceOf<int>() is likely inlined to the constant 1.
    return 0;
}

1. No deducible argument: spaceOf() takes no arguments, so the compiler cannot infer T.
2. Explicit syntax: spaceOf<int>() — the <int> tells the compiler to instantiate with T = int.
3. Compile-time optimization: Since sizeof(T) is a compile-time constant, the entire function can be optimized away, leaving just the constant result.
4. Ceiling division formula: bytes/4 + (bytes%4 > 0 ? 1 : 0) computes \(\lceil \text{bytes}/4 \rceil\).

Answer: spaceOf<int>() = 1, spaceOf<double>() = 2, spaceOf<char>() = 1.

3.7. RANGE Template: Complete Implementation (Tutorial 5, Example 1)

Write a complete implementation of the RANGE template providing:

• Constructor(s) and destructor
• Arithmetic and relational operators (+=, -=, +, -, ==, !=, <, >)
• Increment and decrement operators
• Conversion function RANGE → long
• A checking and exception-handling mechanism

Show two realistic examples of using the RANGE template.

Click to see the solution

Key Concept: Non-type template parameters make the range boundaries part of the type, not the value. This means RANGE<1,12> and RANGE<1,31> are incompatible types — the compiler will flag any mix-up.

#include <iostream>
#include <stdexcept>
using namespace std;

template <int L, int R>
class RANGE {
    int value;

    void check() const {
        if (value < L || value > R)
            throw out_of_range("RANGE value " + to_string(value)
                               + " out of [" + to_string(L) + "," + to_string(R) + "]");
    }

public:
    // Constructor from int
    explicit RANGE(int v) : value(v) { check(); }

    // Copy constructor
    RANGE(const RANGE& r) : value(r.value) { }

    // Destructor (trivial)
    ~RANGE() = default;

    // --- Assignment ---
    RANGE& operator=(const RANGE& r) { value = r.value; return *this; }
    RANGE& operator=(int v)          { value = v; check(); return *this; }

    // --- Compound arithmetic ---
    RANGE& operator+=(int n) { value += n; check(); return *this; }
    RANGE& operator-=(int n) { value -= n; check(); return *this; }

    // --- Binary arithmetic (return plain int for flexibility) ---
    int operator+(int n)          const { return value + n; }
    int operator-(int n)          const { return value - n; }
    int operator+(const RANGE& r) const { return value + r.value; }
    int operator-(const RANGE& r) const { return value - r.value; }

    // --- Increment / Decrement ---
    RANGE& operator++()    { value++; check(); return *this; }  // pre-increment
    RANGE  operator++(int) { RANGE tmp(*this); ++(*this); return tmp; } // post-increment
    RANGE& operator--()    { value--; check(); return *this; }  // pre-decrement
    RANGE  operator--(int) { RANGE tmp(*this); --(*this); return tmp; } // post-decrement

    // --- Relational ---
    bool operator==(const RANGE& r) const { return value == r.value; }
    bool operator!=(const RANGE& r) const { return value != r.value; }
    bool operator< (const RANGE& r) const { return value <  r.value; }
    bool operator> (const RANGE& r) const { return value >  r.value; }

    // --- Conversion to long ---
    operator long() const { return (long)value; }
};

// ---- Practical Examples ----

using DayOfMonth = RANGE<1, 31>;
using MonthOfYear = RANGE<1, 12>;

int main() {
    // Example 1: Calendar date arithmetic
    DayOfMonth   day(15);
    MonthOfYear  month(6);

    cout << "Day: "   << (long)day   << endl;  // 15
    cout << "Month: " << (long)month << endl;  // 6

    ++day;
    cout << "Next day: " << (long)day << endl;  // 16

    try {
        day = 32;  // out of range!
    } catch (const out_of_range& e) {
        cout << "Error: " << e.what() << endl;
    }

    // day = month;  // COMPILE ERROR: incompatible types — safety guaranteed!

    // Example 2: Traffic light phase (0=Red, 1=Yellow, 2=Green)
    using Phase = RANGE<0, 2>;
    Phase light(0);
    for (int i = 0; i < 4; i++) {
        cout << "Light phase: " << (long)light << endl;
        try { ++light; } catch (...) { light = Phase(0); }  // wrap around on overflow
    }

    return 0;
}

1. Template parameters as type identity: DayOfMonth (alias for RANGE<1,31>) and MonthOfYear (RANGE<1,12>) are different types — mixing them is a compile error.
2. check() called on every mutation: constructor, operator=, operator+=, operator++, etc.
3. Conversion to long: Allows printing and using the value in arithmetic expressions without explicit casts.
4. Post-increment: Requires saving a copy before incrementing, returning the old value.

Answer: See complete implementation above. The key insight is that boundary enforcement happens at compile time (type system) and at runtime (exception).

3.8. ARRAY Template with RANGE-based Boundaries (Tutorial 5, Example 2)

Design and implement an ARRAY template where the valid index range is specified as template parameters (using ideas from the RANGE template). The array should support arbitrary index boundaries (not necessarily starting at 0). Implement an indexing operator with bounds checking. Demonstrate with a practical example.

Click to see the solution

Key Concept: Just like RANGE makes the value boundaries part of the type, ARRAY can make the index boundaries part of the type. ARRAY<int,1,12> is an array of 12 integers indexed from 1 to 12 — a “1-based array”.

#include <iostream>
#include <stdexcept>
#include <string>
using namespace std;

// ARRAY<T, Low, High>: an array of type T with indices in [Low, High]
template <typename T, int Low, int High>
class ARRAY {
    static_assert(Low <= High, "ARRAY: Low must be <= High");
    static const int SIZE = High - Low + 1;
    T data[SIZE];

    void checkIndex(int idx) const {
        if (idx < Low || idx > High)
            throw out_of_range("ARRAY index " + to_string(idx)
                               + " out of [" + to_string(Low) + "," + to_string(High) + "]");
    }

public:
    ARRAY() = default;

    // Non-const indexing (allows modification)
    T& operator[](int idx) {
        checkIndex(idx);
        return data[idx - Low];   // Shift: external index → internal 0-based index
    }

    // Const indexing (for read-only access)
    const T& operator[](int idx) const {
        checkIndex(idx);
        return data[idx - Low];
    }

    int low()  const { return Low;  }
    int high() const { return High; }
    int size() const { return SIZE; }
};

int main() {
    // 1-based array of month names (indices 1..12)
    ARRAY<string, 1, 12> monthNames;
    monthNames[1]  = "January";
    monthNames[2]  = "February";
    monthNames[3]  = "March";
    // ... (fill remaining)
    monthNames[12] = "December";

    cout << monthNames[1]  << endl;  // "January"
    cout << monthNames[12] << endl;  // "December"

    try {
        monthNames[0];   // Index 0 is out of range [1, 12]
    } catch (const out_of_range& e) {
        cout << "Error: " << e.what() << endl;
    }

    // 2D array using ARRAY of ARRAYs:
    ARRAY<ARRAY<int, 1, 3>, 1, 3> matrix;
    for (int i = 1; i <= 3; i++)
        for (int j = 1; j <= 3; j++)
            matrix[i][j] = i * 10 + j;

    cout << matrix[2][3] << endl;  // 23

    return 0;
}

1. Index shifting: The internal storage is 0-based (data[0..SIZE-1]). The public interface uses [Low..High]. The translation is data[idx - Low].
2. static_assert: A compile-time assertion that catches invalid template arguments (e.g., ARRAY<int, 10, 5> would fail to compile with a clear message).
3. Two operator[] overloads: One for mutable access (returns T&), one for read-only access on const arrays (returns const T&).
4. 2D array: Nesting ARRAY inside ARRAY gives a 2D structure with full bounds checking on both indices.

Answer: The index shift data[idx - Low] is the key trick. Any index range can be used, and out-of-bounds access is detected at runtime.

3.9. Generic Smart Pointer: RAII Implementation (Tutorial 5, Example 3)

Implement a simple generic smart pointer class template smart_pointer<T> that:

• Takes ownership of a raw pointer passed to its constructor
• Automatically deletes the object when the smart pointer goes out of scope
• Supports -> and * operators for pointer-like usage
• Add operators that make it look as similar to a raw pointer as possible
• Write a test showing the advantage over raw pointers

Click to see the solution

Key Concept: The RAII pattern guarantees that the destructor is called when the object leaves scope — even if an exception is thrown. This is the foundation of all smart pointers.

#include <iostream>
#include <stdexcept>
using namespace std;

template <typename T>
class smart_pointer {
    T* obj;

public:
    // Constructor: acquire ownership
    explicit smart_pointer(T* o = nullptr) : obj(o) { }

    // Destructor: release ownership (RAII core)
    ~smart_pointer() {
        delete obj;
        cout << "[smart_pointer: object deleted]" << endl;
    }

    // Prevent copying (like unique_ptr)
    smart_pointer(const smart_pointer&) = delete;
    smart_pointer& operator=(const smart_pointer&) = delete;

    // Pointer-like operators
    T* operator->() { return obj; }
    T& operator*()  { return *obj; }

    // Conversion to raw pointer (read-only)
    T* get() const { return obj; }

    // Boolean check: is the pointer non-null?
    explicit operator bool() const { return obj != nullptr; }

    // Comparison with nullptr
    bool operator==(nullptr_t) const { return obj == nullptr; }
    bool operator!=(nullptr_t) const { return obj != nullptr; }
};

// A sample class to manage
class Resource {
    int id;
public:
    Resource(int i) : id(i) { cout << "Resource " << id << " created\n"; }
    ~Resource()              { cout << "Resource " << id << " destroyed\n"; }
    void use()               { cout << "Using Resource " << id << "\n"; }
};

void demonstrateAdvantage() {
    // With raw pointers: must remember to delete!
    // Resource* raw = new Resource(99);
    // raw->use();
    // if (someCondition) return;  // MEMORY LEAK if we forget delete here
    // delete raw;

    // With smart_pointer: automatic cleanup, even on early return
    smart_pointer<Resource> sp(new Resource(1));
    sp->use();      // Works like a raw pointer
    (*sp).use();    // Also works

    if (sp) {
        cout << "Pointer is valid\n";
    }

    cout << "Leaving scope...\n";
}   // smart_pointer destructor called automatically here — no delete needed!

int main() {
    demonstrateAdvantage();
    cout << "After scope exit\n";
    return 0;
}

Output:

Resource 1 created
Using Resource 1
Using Resource 1
Pointer is valid
Leaving scope...
[smart_pointer: object deleted]
Resource 1 destroyed
After scope exit

1. RAII: ~smart_pointer() calls delete obj — guaranteed to run when the smart pointer goes out of scope or an exception unwinds the stack.
2. Deleted copy: Prevents two smart_pointer instances from owning the same object (would cause double-delete).
3. operator->: Returns the raw pointer, enabling sp->use() syntax.
4. operator bool(): Allows if (sp) checks.
5. Advantage over raw: Even if demonstrateAdvantage returned early (e.g., exception), the destructor would still run — no memory leak.

Answer: The RAII destructor is the critical mechanism. See output above for the automatic cleanup sequence.